package com.leetcode.根据数据结构分类.链表;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2020/11/19
 * @description: https://leetcode-cn.com/problems/middle-of-the-linked-list/
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * [1,2,3,4,5] -> 3
 */
public class A_876_链表的中间结点 {

	/**
	 * 使用快慢指针
	 * 具象了两种情况：
	 * 奇数：此时临界条件 f.next == null,返回 s;
	 * 偶数：此时临界条件 f==null,返回 s;
	 * --
	 * 在正常模拟了情况下，进行的编码，我觉得这是好的习惯！
	 * @param head
	 * @return
	 */
	public ListNode middleNode(ListNode head) {
		//如果是单节点，直接返回
		if (head.next == null) {
			return head;
		}
		//至少有两个节点
		//1.定义 慢指针
		ListNode slow = head;
		//2.定义 快指针
		ListNode fast = head;
		while (fast != null && fast.next != null) {
			//按照正常流程，slow +1;fast+2
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
}
